package leetcode.code0373;

import java.util.ArrayList;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution2 implements IDebug {
	public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
		int s1 = 0, m1 = 0;
		int s2 = 0, m2 = 0;
		List<List<Integer>> ans = new ArrayList<>();
		int len1 = nums1.length, len2 = nums2.length;
		boolean[][] dp = new boolean[len1][len2];
		while (k > 0 && s1 < len1 && s2 < len2) {
			List<Integer> cur = new ArrayList<>();
//			if (s1 == m2 && s2 == m1) {
//				if (!dp[s1][m1]) {
//					cur.add(nums1[s1]);
//					cur.add(nums2[m1]);
//					dp[s1][m1] = true;
//					ans.add(cur);
//					k--;
//				}
//				m1++;
//				m2++;
//			} else {
				int sum1 = nums1[s1] + nums2[m1];
				int sum2 = nums2[s2] + nums1[m2];
				if (sum1 < sum2) {
					if (!dp[s1][m1]) {
						cur.add(nums1[s1]);
						cur.add(nums2[m1]);
						dp[s1][m1] = true;
						ans.add(cur);
						k--;
					}
					m1++;
				} else {
					if (!dp[m2][s2]) {
						cur.add(nums1[m2]);
						cur.add(nums2[s2]);
						dp[m2][s2] = true;
						ans.add(cur);
						k--;
					}
					m2++;
				}
//			}
			if (m1 == len2) {
				s1++;
				m1 = 0;
			}
			if (m2 == len1) {
				s2++;
				m2 = 0;
			}

		}
//		while (k > 0 && s1 == len1 && m1 == len2 && s2 < len2) {
//			List<Integer> cur = new ArrayList<>();
//			cur.add(nums1[m2]);
//			cur.add(nums2[s2]);
//			m2++;
//			if (m2 == len1) {
//				s2++;
//				m2 = 0;
//			}
//			k--;
//		}
//		while (k > 0 && s2 == len2 && m2 == len1 && s1 < len1) {
//			List<Integer> cur = new ArrayList<>();
//			cur.add(nums1[s1]);
//			cur.add(nums2[m1]);
//			m1++;
//			if (m1 == len2) {
//				s1++;
//				m1 = 0;
//			}
//			k--;
//		}
		return ans;

	}

	@Override
	public void debug1() {
		List<List<Integer>> e = HelpDebug.str2intlist1("[[1,2],[1,4],[1,6]]");
		HelpDebug.compare(e, this.kSmallestPairs(HelpDebug.str2array3("[1,7,11]"), HelpDebug.str2array3("[2,4,6]"), 3));
	}

	@Override
	public void debug2() {
		List<List<Integer>> e = HelpDebug.str2intlist1("[[1,3],[2,3]]");
		HelpDebug.compare(e, this.kSmallestPairs(HelpDebug.str2array3("[1,2]"), HelpDebug.str2array3("[3]"), 3));
	}

	@Override
	public void debug3() {
		List<List<Integer>> e = HelpDebug.str2intlist1("[[1,1],[1,1]]");
		HelpDebug.compare(e, this.kSmallestPairs(HelpDebug.str2array3("[1,1,2]"), HelpDebug.str2array3("[1,2,3]"), 2));
	}

	@Override
	public void debug4() {
		List<List<Integer>> e = HelpDebug.str2intlist1("[[1,1],[1,1],[2,1],[1,2],[1,2],[2,2],[1,3],[1,3],[2,3]]");
		HelpDebug.compare(e, this.kSmallestPairs(HelpDebug.str2array3("[1,1,2]"), HelpDebug.str2array3("[1,2,3]"), 10));
	}
	public void debug5() {
		List<List<Integer>> e = HelpDebug.str2intlist1("[[-10,3],[-10,5],[-10,6],[-10,7],[-10,8],[-4,3],[-4,5],[-4,6],[0,3],[0,3]]");
		HelpDebug.compare(e, this.kSmallestPairs(HelpDebug.str2array3("[-10,-4,0,0,6]"), HelpDebug.str2array3("[3,5,6,7,8,100]"), 10));
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
//		so.debug1();
//		so.debug2();
//		so.debug3();
		so.debug4();
		so.debug5();

	}

}
